Although they are very interesting for modeling heterogeneous structures, computational homogenization schemes are well-known to require significant computational resources. This computational cost stems from the solution of fine scale problems which are small in size but great in number [1]. In this work, inspired from a recent study |2], it is proposed to accelerate these simulations by clustering the structure’s integration points based on local strains. At each iteration of the structure scale nonlinear solver, the k-medoid clustering algorithm is used to associate each integration point to a medoid. Then, fine scale problems are solved only for medoids. Appropriate interpolation formula are developed for assigning stresses and tangent modulii to all the structure’s elements from the associated medoids, and also for updating internal variables for each fine scale model. Because the number of fine scale problems to solve is reduced, the proposed clustering-accelerated computational homogenization scheme is a promising candidate to reduce the computational cost of finite element squared (FE²) simulations. Results on various problems involving different nonlinear material behavior laws show the interest of this approach.